1. Field of the Invention
This invention relates to a cryptographic key recovery system and, more particularly, to a key recovery system that is interoperable with existing systems for establishing keys between communicating parties.
2. Description of the Related Art
Data encryption systems are well known in the data processing art. In general, such systems operate by performing an encryption operation on a plaintext input block, using an encryption key, to produce a ciphertext output block. The receiver of an encrypted message performs a corresponding decryption operation, using a decryption key, to recover the plaintext block.
Encryption systems fall into two general categories. Symmetric (or private key) encryption systems such as the Data Encryption Standard (DES) system use the same secret key for both encrypting and decrypting messages. In the DES system, a key having 56 independently specifiable bits is used to convert 64-bit plaintext blocks to ciphertext blocks, or vice versa.
Asymmetric (or public key) encryption systems, on the other hand, use different keys that are not feasibly derivable from one another for encryption and decryption. A person wishing to receive messages generates a pair of corresponding encryption and decryption keys. The encryption key is made public, while the corresponding decryption key is kept secret. Anyone wishing to communicate with the receiver may encrypt a message using the receiver's public key. Only the receiver may decrypt the message, however, since only he has the private key. Perhaps the best-known asymmetric encryption system is the RSA encryption system, named after its originators Rivest, Shamir and Adleman.
Asymmetric encryption systems are generally more computationally intensive than symmetric encryption systems, but have the advantage that they do not require a secure channel for the transmission of encryption keys. For this reason, asymmetric encryption systems are often used for the one-time transport of highly sensitive data such as symmetric encryption keys.
Data encryption systems of all types have attracted the attention of government intelligence agencies and law enforcement agencies, since the same cryptographic strength that prevents decryption by unauthorized third parties also prevents decryption by intelligence or law enforcement officials having a legitimate reason for wanting to access the plaintext data. Because of such concerns, governments have either prohibited the use or export of strong encryption systems or have conditioned their approval on the use of weakened keys that are susceptible to key-exhaustion attacks (i.e., systematically testing all possible keys until the right one is found). Such weak encryption systems have the obvious disadvantage that they are just as vulnerable to unauthorized third parties as they are to authorized government officials.
Various cryptographic key recovery systems have recently been proposed as a compromise between the demands of communicating parties for privacy in electronic communications and the demands of law enforcement agencies for access to such communications when necessary to uncover crimes or threats to national security. Generally, in such key recovery systems, all or part of the key used by the communicating parties is made available to one or more key recovery agents, either by actually giving the key portions to the key recovery agents (in which case the key portions are said to be "escrowed") or by providing sufficient information in the communication itself (as by encrypting the key portions) to allow the key recovery agents to regenerate the key portions. Key recovery agents would reveal the escrowed or regenerated key portions to a requesting law enforcement agent only upon presentation of proper evidence of authority, such as a court order authorizing the interception.
The use of multiple key recovery agents, all of which must cooperate to recover the key, minimizes the possibility that a law enforcement agent can improperly recover a key by using a corrupt key recovery agent.
Key recovery systems serve the communicants' interest in privacy, since their encryption system retains its full strength against third parties and does not have to be weakened to comply with domestic restrictions on encryption or to meet export requirements. At the same, key recovery systems serve the legitimate needs of law enforcement by permitting the interception of encrypted communications in circumstances where unencrypted communications have previously been intercepted (as where a court order has been obtained).
In addition to serving the needs of law enforcement, key recovery systems find application in purely private contexts. Thus, organizations may be concerned about employees using strong encryption of crucial files where keys are not recoverable. Loss of keys may result in loss of important stored data.
A number of desirable features of a key recovery system have been identified. Thus, considering first higher-priority features, a key recovery system should be capable of being implemented in software or hardware. It should not require communication with a third party during message creation or connection setup. It should provide interoperability between users in different countries. The algorithms used should be publicly known, and the mechanism should be algorithm independent. The design should be open and should be capable of being implemented by multiple vendors based on published specifications. It should provide a key recovery capability independently for each country. It should provide, in a single system, the flexibility for different levels of security in different environments, and provide the highest level of cryptographic security allowable by law. It should be a modular extension (add-on) to existing cryptographic systems. It should permit any key exchange mechanism to be used, while retaining a control point that enforces compliance with key recovery. The security properties of the exchanged key should be maintained, except for allowing for recovery.
Other features, though of lesser priority, are nevertheless highly desirable. A key recovery system should support both store-and-forward and interactive environments. It should not require communication with a third party for installation (i.e., it should work "out of the box"). It should support the policy option of requiring the collaboration of multiple key recovery agents to recover the key (to provide protection against a corrupt key recovery agent). It should allow an external verifier (without access to the key recovery keys) to have some level of confidence that the parties use an unpatched implementation of this system. (Note that in interactive environments, if both parties encrypt with the same public keys and key recovery information, a third party can check for equality of ciphertexts.) It should prevent a patched (rogue) implementation from interoperating with an unpatched (complying) implementation. It should be hard to subvert the scheme to use it for a bulk data confidentiality channel.
Key recovery systems of various types are described in D. E. Denning and D. K. Branstad, "A Taxonomy for Key Escrow Encryption Systems", Communications of the ACM, vol. 39, no. 3, Mar. 1996, pp. 34-40, incorporated herein by reference. Two specific key recovery systems are noted below.
The copending application of D. B. Johnson et al., Ser. No. 08/629,815, filed Apr. 10, 1996, entitled "Cryptographic Key Recovery System", describes a partial key recovery system using multiple key recovery agents. In one version of the system described in that application, the sender generates a set of key recovery values (or key parts) P, Q and (optionally) R. The session key is created by combining the P and Q values by XOR addition, concatenating the result with R, and hashing the concatenation result to generate the key. The P and Q values are then encrypted using the public keys of the respective key recovery agents and the encrypted P and Q values included (along with other recovery information) in a session header accompanying the encrypted message. The R value, if generated, is not made available to any key recovery agent, but is kept secret to provide a nontrivial work factor for law enforcement agents seeking to recover the key.
As is evident from the above description, the key recovery procedure described in the copending application requires the secret session key used for encrypting messages to be established using the mechanism of the key recovery procedure itself. Since users cannot independently specify the session key, the disclosed key recovery procedure is incompatible with existing key agreement procedures.
In another key recovery system, described in PCT patent publication WO 96/05673 (Trusted Information Systems, Inc.), the sender splits a session key into first and second session key portions by setting the first session key portion equal to a random number and setting the second session key portion equal to the XOR product of the random number and the session key. The sender creates a law enforcement access field (LEAF) by encrypting the respective session key portions with the public encryption keys of first and second key recovery agents and concatenating the two encryption products. The sender also creates a LEAF verification string (LVS) by concatenating the original session key portions and encrypts this using the session key to form an encrypted LEAF verification string (ELVS). Finally, the sender transmits an encrypted message, together with the LEAF and ELVS, to the receiver.
Before decrypting the encrypted message, the receiver regenerates the LEAF to verify that the sender has created a proper LEAF that would actually permit recovery of the session key through the key recovery agents. This is done by decrypting the ELVS to obtain the session key portions and then encrypting the respective session key portions with the public encryption keys of first and second key recovery agents. If the receiver succeeds in regenerating the transmitted LEAF in this manner, it concludes that the LEAF is genuine and proceeds to decrypt the message. Otherwise, it concludes that the LEAF is corrupt and does not proceed with the decryption step.
While this latter key recovery system allows the use of arbitrarily generated session keys, it does so by introducing an additional secret quantity (the random number) that the receiver does not have into the key-splitting procedure. Because of this additional secret quantity, the receiver cannot independently regenerate the key portions (to validate the LEAF), but must obtain them as additional information from the sender (by means of the ELVS).